home *** CD-ROM | disk | FTP | other *** search
/ Group 42-Sells Out! - The Information Archive / Group 42 Sells Out (Group 42) (1996).iso / crypto / 2xisolat.txt < prev    next >
Text File  |  1995-11-30  |  10KB  |  258 lines
  1.    2x Isolated Double-DES: Another Weak Two-Level DES Structure
  2.  
  3.  
  4.  
  5. Introduction
  6.  
  7. The time has come to replace DES, the US Data Encryption Standard,
  8. but there is no clear alternative.  While there are many ciphers
  9. which are demonstrably faster and also arguably stronger than DES,
  10. the fact that cipher strength cannot be _tested_ but must instead
  11. be_argued_ makes many users nervous.  The US government offers some
  12. alternative ciphers, but those are secret designs whose strength
  13. _cannot_ be argued, again making users nervous.
  14.  
  15. The current leading candidate for a replacement to DES is "triple-
  16. DES," a three-level construct using DES at each level.  This is a
  17. comforting design, because users are already convinced that DES
  18. can be relied upon for a certain level of strength.  Unfortunately,
  19. a software implementation of triple-DES takes three times the
  20. processing of normal DES.  While this is a mere detail on systems
  21. which process the occasional enciphered email message, operational
  22. speed is fundamental to widespread industrial use.  Ciphering speed
  23. is essential in LAN servers and other fully-enciphered communications
  24. nodes.  Speed is also important when ciphering is an integral part
  25. of laptop software which communicates to a central facility.  Fast
  26. software ciphering is important.
  27.  
  28. Because the ciphering speed for triple-DES is not acceptable, no
  29. three-or-more-level construct could possibly be satisfactory in
  30. this respect.  This limits our design alternatives to one-or two-
  31. level constructs based on DES.
  32.  
  33. The goal, then, is to find--if possible--a construct which is based
  34. on DES, has strength substantially beyond normal DES, but requires
  35. less processing than triple-DES.  This time we start from the base
  36. of double-DES, and directly confront the known weakness of that
  37. approach:
  38.  
  39.  
  40. Double-DES
  41.  
  42. The classical double-DES construct is something like this:
  43.  
  44.             A
  45.             v
  46.      k1 -> DES1
  47.             v
  48.             B
  49.             v
  50.             C
  51.             v
  52.      k2 -> DES2
  53.             v
  54.             D
  55.  
  56. where each single capital letter represents an 8-byte DES block.
  57. Double-DES is normally not used, because of the meet-in-the-middle
  58. attack:
  59.  
  60.  
  61. Meet-In-The-Middle Attack on Double DES
  62.  
  63. Assume we have known-plaintext A for ciphertext D:  Encipher A
  64. under every possible key k1, and decipher D under every possible
  65. key k2.  (The cost for this is only two full DES key searches.)
  66. Then check for matches between B and C.  If there are multiple
  67. matches, the correct k1 and k2 will be there somewhere, and we
  68. can isolate the correct pair with one or two more known-plaintext
  69. blocks (this is a loose interpretation of [2]).
  70.  
  71. This works for the normal double-DES construction because it is
  72. possible to check for matches between B and C; the weakness seems
  73. to be the ability to check for a match.  Assuming that we have
  74. properly identified the principal weakness of double-DES, let's
  75. fix it:  We can isolate the two values, making a match check
  76. impossible, so that not even one bit can be checked.
  77.  
  78.  
  79. Isolated Double-DES
  80.  
  81. Consider a two-level DES construct like this:
  82.  
  83.             A
  84.             v
  85.      k1 -> DES1
  86.             v
  87.             B
  88.             v
  89.      km -> XOR
  90.             v
  91.             C
  92.             v
  93.      k2 -> DES2
  94.             v
  95.             D
  96.  
  97. where k1 and k2 are 56-bit keys, but km is a 64-bit key.
  98. Technically, this construct could be considered to be either
  99. double-DES with an intermediate ("isolating") XOR operation, or
  100. triple-DES with XOR replacing the middle DES operation.  But since
  101. the processing cost for this system is similar to double-DES, it
  102. is reasonable to call it a form of double-DES.
  103.  
  104. While it is true that we now have three keys for a two-level DES
  105. structure, this is no worse than triple-DES with separate keys.
  106. But is it stronger than double-DES?
  107.  
  108.  
  109. Isolated Double-DES Meet-In-The-Middle Attack
  110.  
  111. Again, encipher A under every possible key k1, and decipher D under
  112. every possible key k2 and check for matches between B and C.
  113.  
  114. But in the isolated construction, every possible pair of values
  115. (B,C) has some key km which would make that pair match.  Thus, the
  116. weakness of match identification in the original construction is
  117. not possible in the alternate construction.
  118.  
  119. The keyspace seems to be 56 + 64 = 120 bits, which would probably
  120. be satisfactory for another couple of decades, or until an open
  121. science of cryptographic machine design has matured.  It still
  122. has a small block size, however.
  123.  
  124.  
  125. Larger Blocks
  126.  
  127. DES uses a relatively-small 8-byte block, so if DES were used
  128. in Electronic Code Book (ECB) mode and large amounts of plaintext
  129. were known, a dictionary attack would be possible.  Fortunately, DES
  130. is normally used in Cipher Block Chain (CBC) mode, making dictionary
  131. attacks difficult.  But a dictionary attack on ECB mode could be
  132. viewed as a "certificational attack" which is "indicative of
  133. weakness" in the cipher itself. [1:466]
  134.  
  135. If we make the modest assumption that ordinary text has an
  136. information content of under 40 percent of the binary size, then
  137. a 64-bit block of text generally contains less than 26 bits of
  138. uniqueness.  Worse, short words occur far more often than an even
  139. distribution would indicate.  Although it would certainly be ill-
  140. advised to send 2^26 blocks (2^29 bytes) of data under a single set
  141. of keys, it is interesting to note the relatively small size of this
  142. figure when compared to other cryptographic quantities.
  143.  
  144. For this reason, it seems appropriate that any new standard specify
  145. an expanded block width.  Here is a double-width approach, 2x2 DES
  146. described in an earlier article:
  147.  
  148.              A             B
  149.              v             v
  150.       k1 -> DES1    k2 -> DES2
  151.              v             v
  152.              C             D
  153.           Exchange Right 4 Bytes
  154.              E             F
  155.              v             v
  156.       k3 -> DES3    k4 -> DES4
  157.              v             v
  158.              G             H
  159.  
  160. Note that the 64-bit quantity G (for example) is a complex nonlinear
  161. function of A, B, k1, k2, and k3; a total of 296 bits.  Nevertheless
  162. the system is still solvable with meet-in-the-middle:
  163.  
  164.  
  165. 2x2 DES Meet-In-The-Middle Attack
  166.  
  167. With one known-plaintext block, we can search one top key and one
  168. bottom key (say, k1 and k3) and find pairs (E,C) which match at the
  169. appropriate 32 bit-positions.  Then we can identify the correct
  170. pair with additional known-plaintext blocks, resolving the keys at
  171. 32-bits per known-plaintext pair.
  172.  
  173. We can guarantee that the two keys will be found by searching all
  174. possible k1 and k3.  This is only twice the normal DES keyspace,
  175. but may well require a huge amount of storage to identify all the
  176. values and associated keys (say, E and k3) which match a particular
  177. result (say, C).  We do not want to run through every k3 every
  178. time we change k1.
  179.  
  180.  
  181. 2x2 DES Differential Attack
  182.  
  183. Eli Biham [1] points out that a differential attack can eliminate
  184. the need to store the result from every possible key.  In this case
  185. we need two different large blocks of known-plaintext with plaintext
  186. or ciphertext half the same (say, A:B -> G:H and A:X -> Y:Z).  With
  187. A the same in both large blocks, we know that the left-half of E
  188. must also be the same.  Then, since we have two different blocks, we
  189. can step through all possible values for k3, deciphering G into E
  190. and Y into E' each time, looking for any results with the left-half
  191. the same.  This should occur about every 2^32 trials, producing 2^24
  192. trials which match, which should be resolved in only one or two more
  193. set of known-plaintext blocks.  No huge storage is needed.
  194.  
  195.  
  196. 2x Isolated Double-DES
  197.  
  198. Consider a pair of isolated double-DES structures, combined as
  199. described for 2x2 DES:
  200.  
  201.             A              B
  202.             v              v
  203.      k1 -> DES1     k2 -> DES2
  204.             v              v
  205.      km -> XOR1     kn -> XOR2
  206.             v              v
  207.          Exchange Right 4 Bytes
  208.             v              v
  209.      k3 -> DES3     k4 -> DES4
  210.             v              v
  211.             C              D
  212.  
  213. The result is a double-width structure, in which every ciphertext
  214. bit in C depends on each and every bit in A, B, k1, k2, and k3, as
  215. well as half the bits in km and kn.  Ciphering occurs at the rate
  216. of double-DES.  While it is certainly true that six keys are needed,
  217. keys need be transmitted far less often than data, and by having
  218. separate keys we avoid attacks which depend upon having the same
  219. key at multiple parts of the operation.  If we say that enciphering
  220. occurs "from the top down," (XOR before exchange) then we would say
  221. that deciphering occurs "from the bottom up" (exchange before XOR).
  222.  
  223.  
  224. 2x Isolated Double-DES Meet-In-The-Middle Attack
  225.  
  226. The double-DES meet-in-the-middle attack depended upon having a
  227. structure in which the enciphered plaintext was identical to the
  228. deciphered ciphertext.  This allowed both keys to be manipulated
  229. and the resulting data space searched for matches.
  230.  
  231. In isolated double-DES any enciphered plaintext value can be
  232. related to any deciphered ciphertext value by varying the middle
  233. or "isolating" key.  Thus, meet-in-the-middle seems not very useful.
  234.  
  235.  
  236. 2x Isolated Double-DES Differential Attack
  237.  
  238. The 2x2 differential attack depended not upon identical top and
  239. bottom values, but upon producing an identical value (in particular
  240. known bit positions) from a bottom deciphering (for example).  This
  241. situation is not affected by the XOR and so the differential attack
  242. will still work.
  243.  
  244.  
  245. Conclusion
  246.  
  247. 2x Isolated double-DES falls to a differential attack.
  248.  
  249.  
  250. References
  251.  
  252. [1]  Biham, E.  Mon, 7 Feb 1994 16:59:28 GMT.  Comments on Nx2 DES.
  253.      <CKv5v5.EnF@chinet.chinet.com>
  254.  
  255. [2]  Merkle, R. and M. Hellman.  1981.  On the Security of Multiple
  256.      Encryption.  Communications of the ACM.  24(7): 465-467.
  257.  
  258.